Data communication networks refer to resources which interconnect and provide for communications between various computers, telephones, and other network users that are located at geographically separate locations. These networks can range from small networks interconnecting computers within a building to large distributed networks spanning countries or continents. Data communications networks are typically implemented where a large number of users interact or share resources, as such networks allow sharing of communications resources in a cost-effective manner.
Data communications networks are comprised of a group of switches, which are referred to as nodes, and a plurality of transmission links which interconnect the nodes. The nodes serve to provide users access to the network, and provide means for routing data transmitted across the network. The transmission links which interconnect these nodes carry the communications signals, and may comprise one or more different types of communications media such as wire, cable, radio, satellite or fiber optic communications links.
Networks provide for communications between users by transmitting data over one or more "transmission" or "routing" paths, which refer to the sequential series of nodes the data traverses in traveling from a source node to the destination node. These transmission paths connect the node at which the originator of the transmission request is located (i.e., the source node) to the node at which the recipient of the data is located (i.e., the destination node). Once such a path is established, part or all of the data is transmitted from the source node to the next node on the routing path via a transmission link, and thereafter retransmitted to additional intermediate nodes until the data ultimately reaches the destination node.
Data communications networks may operate via circuit-switching, packet-switching, or a combination of the two. In circuit-switched networks, a private transmission path is created through the network in response to a transmission request. This private path is held for the duration of the communication between the source node and the destination node, and other users are not allowed access to the resources comprising the routing path until after the entire communication has been completed. In packet-switched networks, blocks of data (data packets) are once again transferred from the source node to the destination node along a path in the network, but blocks of data which are part of the same communication need not always use the same path. Moreover, as a particular path in the network is not reserved for any particular communication, network users may share the same resources during the course of a single communication.
As communications resources are shared in packet switched networks, they are not always instantaneously available when a packet arrives at a particular intermediate node in the network. As such, data packets may be stored temporarily in buffers at intermediate nodes as they wait for transmission resources to the next node to become available. The time period during which a data packet is stored in buffers at an intermediate node is referred to as the queuing delay at the intermediate node. Moreover, since data packets comprising a single communication may be routed through the network via different paths, the packets comprising the communication may also experience different propagation delays. Because data packets may be subject to different propagation and queuing delays, it is possible that the data which comprises a single communication may not be received at the destination in the proper order. Consequently, resources may be required at the destination nodes for buffering and reordering received data packets so that the network provides the communication to the end user in the proper sequence.
The queuing and propagation delays associated with packet-switched networks can be problematic because certain types of communications signals, such as two-way voice communications, can only tolerate very short delays. In this situation, if the network cannot guarantee transmission of the communication within some minimum amount of time, the originating user will typically be given a "busy" signal. As such "busy" signals are undesirable, one of the primary goals of most networks is to efficiently assign transmission resources so as to minimize the number of times when the network is unable to guarantee transmission of a communication within the time period specified for that particular communication.
The maximum acceptable delay time specified for a particular communication may be expressed in a variety of different ways, such as in terms of the total delay, the difference in delay between the slowest and fastest blocks of data transmitted, or delay as a percentage of propagation time. Which criteria is specified depends on the types of communications transmitted across the network, as different delay parameters are important for different types of communications. Typically, all the users accessing a particular network specify their delay requirements in terms of a common delay criteria, and the network assigns resources in a manner that attempts to ensure that the delay requirements of each individual link are satisfied.
Most current networks use some form of "shortest path" routing to select routing paths in response to user communications requests. A general description of shortest path routing is given in Mischa Schwartz, Telecommunication Networks: Protocols, Modeling and Analysis, (1987) pp. 267-282. These shortest path routing algorithms attempt to either assign the "shortest path" to each transmission request (i.e., the path through the network resulting in the smallest delay), or, alternatively, simply attempt to ensure that each transmission request is assigned a path that has an associated delay less than the maximum delay specified for the transmission request. Current shortest path algorithms often take into account other parameters of the network, such as the bandwidth constraints of the various network transmission links, to optimize network performance.
By way of example, a reasonably sophisticated example of a "shortest path" path selection procedure is the procedure used in the Network Broadband Services ("NBBS") architecture, which is discussed in detail in Te Tedijanto, et al., NBBS Path Selection Framework, IBM Systems Journal, Vol. 34, No. 4, 1995, pp. 629-639. While the details of the NBBS path selection procedure are relatively complex, at its most basic level, the algorithm computes, for each number of hops h (where a "hop" is a single processing node in the network), the lowest delay from a source node s to each node in the network. This is accomplished, through an iterative process, by adding the delay values associated with each transmission link which serves to connect a particular node to its neighboring nodes to the (already computed) delay value associated with transmitting the signal from the source node to the appropriate neighboring node. These sums are then compared to identify the path which results in the lowest delay to the particular node in question. Thus, for instance, if the delay requirement is the total delay (which comprises the propagation delay added to the queuing delay), then for each transmission link i which connects node x to a neighboring node, the propagation delay and queuing delay for link i is added to the previously calculated total delay associated with transmitting a signal to the neighboring node. In this manner, the total delays to node x associated with routing a signal through each node neighboring node x are computed, and the lowest of these values is the total delay to node x.
Shortest path routing algorithms are designed to ensure that a single "cost" criteria, such as the total delay or the variable delay, is minimized or satisfied. As such, these algorithms are not suitable for identifying routing paths which satisfy two or more "cost" criteria. This may be problematic, because in transmitting certain types of data it may be necessary to ensure that more than one of the different delay parameters is held below some maximum value.
By way of example, with voice communications, the relevant delay parameter is typically the total delay, as the goal is to provide a two-way communications link which does not have a noticeable transmission delay. However, when transmitting broadband video signals, the total delay is often irrelevant (since these are primarily one-way, not two-way, communications), but the queuing delay may be very important as only limited buffering is typically available. Accordingly, for applications that combine voice and video communications signals (e.g., video-teleconferencing), current network optimization algorithms are less than ideal as they typically are unable to ensure that both the criteria for voice and video are satisfied.
One potential method of identifying routing paths that satisfy multiple delay requirements is to calculate each of the multiple delays associated with every communication path in the network. While such an approach would identify any suitable paths, the computing resources and time required to perform such computations are prohibitively high in practical networks, as the computations required grows exponentionally with the size of the network. As such, networks faced with this problem have instead sought to combine the multiple criteria into a single, restrictive criteria. However, use of this more restrictive criteria leads to unsatisfactory results in actual operation, as often no path exists which satisfy the more restrictive criteria.
By way of example, when a video-teleconferencing signal is communicated across a network it may be necessary to ensure that the total delay is less than a first specified limit (c.sub.1) and that the queuing delay (Q) is less than a second specified limit (c.sub.2). The total delay is comprised of the propagation delay (P) and the queuing delay. Thus, the delay criterion can be described mathematically as: EQU P+Q.ltoreq.c.sub.1 (1a) EQU Q.ltoreq.c.sub.2 (1b)
One way of ensuring that the criteria of Equations (1a) and (1b) are satisfied is to find a network routing path which satisfies the more restrictive criteria of P+Q.ltoreq.c.sub.2. However, such an approach imposes an artificially strict delay requirement (as c.sub.2 is typically much smaller than c.sub.1), and as such, in most practical networks there is rarely a path which satisfies the P+Q.ltoreq.c.sub.2 delay criteria. This is particularly true in geographically dispersed networks, because c.sub.2 (which is driven by buffering resources) will often be smaller than the minimum possible propagation delay, thereby guaranteeing that no path can exist which will satisfy P+Q.ltoreq.c.sub.2. For example, in the case of a real-time connection across the continental United States, the propagation delay (P) is on the order of 20 milliseconds, while the maximum queuing delay (Q) may be limited to 3-5 milliseconds. In such a case, it is theoretically impossible to find a path where P+Q.ltoreq.c.sub.2 since P is greater than c.sub.2. Accordingly, using the combined criteria is typically not an acceptable solution to the problem of identifying network routing paths that meet two separate delay requirements.
Various standard committees, including the International Union of Telecommunications and the ATM Forum have recognized the need for path selection algorithms that guarantee that a network path is provided that satisfies two separate criteria. However, despite the recognized need for network path selection algorithms that account for multiple delay requirements, prior solutions may be either impractical or ineffective at selecting paths which satisfy two or more separate requirements. As such, there exists a need for improvement in the algorithms used to select routing paths through networks. More specifically, a need exists for new methods of determining paths which satisfy multiple delay requirements, that may be carried out by existing network computing resources, and which are capable of identifying acceptable routing paths most of the time in realistic networks.